/**
 * @file eigen_algorithms.h
 *
 * Some useful algorithms applied to Eigen classes
 * 
 * @author Dahua Lin
 */

#ifndef SLIPP_EIGEN_ALGORITHMS_H_
#define SLIPP_EIGEN_ALGORITHMS_H_

#include <slipp/eigen_ex/eigen_common.h>
#include <functional>
#include <algorithm>

namespace sli
{
	/********************************************
	 *
	 *  Sorting
	 *
	 ********************************************/

	namespace _detail
	{
		template<typename ValueType, typename IndexType>
		struct indexed_value
		{
			ValueType v;
			IndexType i;

			void set(const ValueType& v_, const IndexType& i_)
			{
				v = v_;
				i = i_;
			}
		};

		template<typename ValueType, typename IndexType, class Comp>
		struct indexed_value_comparer
		{
			Comp comp;

			indexed_value_comparer(Comp comp_) : comp(comp_) { }

			bool operator() (
					const indexed_value<ValueType, IndexType>& lhs,
					const indexed_value<ValueType, IndexType>& rhs)
			{
				return comp(lhs.v, rhs.v);
			}
		};

	}

	// inplace sort

	template<class Derived, class Comp>
	inline void inplace_sort(Eigen::PlainObjectBase<Derived>& x, Comp comp)
	{
		std::sort(x.data(), x.data() + x.size(), comp);
	}

	template<class Derived>
	inline void inplace_sort_asc(Eigen::PlainObjectBase<Derived>& x)
	{
		typedef typename Eigen::PlainObjectBase<Derived>::Scalar scalar_type;
		inplace_sort(x, std::less<scalar_type>());
	}

	template<class Derived>
	inline void inplace_sort_des(Eigen::PlainObjectBase<Derived>& x)
	{
		typedef typename Eigen::PlainObjectBase<Derived>::Scalar scalar_type;
		inplace_sort(x, std::greater<scalar_type>());
	}


	// sort

	template<class DerivedIn, class DerivedOut, class Comp>
	inline void sort(const Eigen::DenseBase<DerivedIn>& x, Eigen::PlainObjectBase<DerivedOut>& sx, Comp comp)
	{
		sx.derived() = x.derived();
		inplace_sort(sx, comp);
	}

	template<class DerivedIn, class DerivedOut>
	inline void sort_asc(const Eigen::DenseBase<DerivedIn>& x, Eigen::PlainObjectBase<DerivedOut>& sx)
	{
		typedef typename Eigen::DenseBase<DerivedIn>::Scalar scalar_type;
		sort(x, sx, std::less<scalar_type>());
	}

	template<class DerivedIn, class DerivedOut>
	inline void sort_des(const Eigen::DenseBase<DerivedIn>& x, Eigen::PlainObjectBase<DerivedOut>& sx)
	{
		typedef typename Eigen::DenseBase<DerivedIn>::Scalar scalar_type;
		sort(x, sx, std::greater<scalar_type>());
	}


	// sort_with_index

	template<class DerivedIn, class DerivedOut, class DerivedIdx, class Comp>
	void sort_with_index(const Eigen::DenseBase<DerivedIn>& x,
			Eigen::PlainObjectBase<DerivedOut>& sx, Eigen::PlainObjectBase<DerivedIdx>& idx, Comp comp)
	{
		typedef typename Eigen::DenseBase<DerivedIn>::Scalar value_type;
		typedef typename Eigen::PlainObjectBase<DerivedIdx>::Scalar index_type;

		typedef _detail::indexed_value<value_type, index_type> entry_t;

		const typename eigen_evaluated_type<DerivedIn>::type& ex = x.eval();

		EIGEN_AROW(entry_t) entries(ex.size());
		entry_t *pe = entries.data();

		const value_type *px = ex.data();
		index_type n = (index_type)(ex.size());

		for (index_type i = 0; i < n; ++i)
		{
			pe[i].set(px[i], i);
		}

		_detail::indexed_value_comparer<value_type, index_type, Comp> comparer(comp);

		std::sort(pe, pe+n, comparer);

		sx.resize(x.rows(), x.cols());
		idx.resize(x.rows(), x.cols());

		typename Eigen::DenseBase<DerivedOut>::Scalar* psx = sx.data();
		index_type *pidx = idx.data();

		for (index_type i = 0; i < n; ++i)
		{
			const entry_t& e = pe[i];
			psx[i] = e.v;
			pidx[i] = e.i;
		}
	}


	template<class DerivedIn, class DerivedOut, class DerivedIdx>
	inline void sort_with_index_asc(const Eigen::DenseBase<DerivedIn>& x,
			Eigen::PlainObjectBase<DerivedOut>& sx, Eigen::PlainObjectBase<DerivedIdx>& idx)
	{
		typedef typename Eigen::DenseBase<DerivedIn>::Scalar scalar_type;
		sort_with_index(x, sx, idx, std::less<scalar_type>());
	}

	template<class DerivedIn, class DerivedOut, class DerivedIdx>
	inline void sort_with_index_des(const Eigen::DenseBase<DerivedIn>& x,
			Eigen::PlainObjectBase<DerivedOut>& sx, Eigen::PlainObjectBase<DerivedIdx>& idx)
	{
		typedef typename Eigen::DenseBase<DerivedIn>::Scalar scalar_type;
		sort_with_index(x, sx, idx, std::greater<scalar_type>());
	}

}

#endif 
